function LinkedList() {

    // 封装一个Node类，用于保存每个节点信息
    function Node(element) {
        this.element = element;
        this.next = null;
    }

    // 链表中的属性
    this.length = 0; // 链表的长度
    this.head = null; // 链表的第一个节点

    // 链表中的方法
    LinkedList.prototype.append = function (element) {

        var node = new Node(element);

        // 链表为空
        if (this.head === null) {
            this.head = node;
        } else {
            // 链表不为空
            var current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            // 这时候current指向最后一个node
            current.next = node
        }

        // 链表长度增加1
        this.length++
    }

    LinkedList.prototype.get = function (index) {
        // 先判断是否超出范围
        if (index < 0 || index >= this.length) return;
        let cur = this.head;
        for (let i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    LinkedList.prototype.toString = function () {
        // 定义两个变量
        var current = this.head;
        var listString = '';

        // 2循环获取链表中所有元素
        while (current !== null) {
            listString += ',' + current.element
            current = current.next
        }

        return listString.slice(1)
    }

    LinkedList.prototype.insert = function (position, element) {
        // 给出要插入的位置和插入的值
        // 先判断position的范围，违规的范围返回false
        if (position < 0 || position > this.length) return false;

        // 创建新节点
        var newNode = new Node(element);
        // 有两种情况，插入最开始的头部和其他
        if (position == 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            var current = this.head;
            var previous = null;
            for (var i = 0; i < position; i++) {
                previous = current;
                current = current.next;
            }
            // 插入完成
            newNode.next = current;
            previous.next = newNode;
        }

        this.length++;
        return true;
    }


    // 根据位置移除数据
    LinkedList.prototype.removeAt = function (position) {
        if (position < 0 || position > this.length) return null;

        var current = this.head;

        // 第一种情况，删除的数字是第一个
        if (position === 0) {
            this.head = this.head.next;
        } else {
            // 第二种情况，删除的是别的位置
            var previous = null;
            for (var i = 0; i < position; i++) {
                previous = current;
                current = current.next;
            }
            // 删除
            previous.next = current.next;
        }
        this.length--;
        return current.element;
    }

    LinkedList.prototype.deleteAtIndex = function (index) {
        // 是删除第 index 个节点
        // 不是删除 索引为 index 的节点
        // 判断 index 是否超出范围
        if (index <= 0 || index > this.length) return;
        let cur = this.head;
        // 删除的是头节点
        if (index == 1) {
            this.head = this.head.next;
        } else {
            for (let i = 0; i < index - 2; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
    }

    LinkedList.prototype.get = function (index) {
        if (index < 0 || index >= this.length) return;
        let cur = this.head;
        for (let i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.element;
    }


    // 获取元素的位置
    LinkedList.prototype.indexOf = function (element) {

        var current = this.head;

        for (var i = 0; i < this.length; i++) {
            if (element === current.element) {
                return i;
            } else {
                // 继续找
                current = current.next;
            }
        }

        // 没找到，返回-1
        return -1;
    }

    // 根据元素删除
    LinkedList.prototype.remove = function (element) {
        var index = this.indexOf(element);
        return this.removeAt(index)
    }

    // update方法
    LinkedList.prototype.update = function (position, element) {

        if (position < 0 || position >= this.length) return null;
        // 如果是第一个
        if (position === 0) {
            this.head.element = element;
        } else {
            var current = this.head;
            for (var i = 0; i < position; i++) {
                current = current.next;
            }
            // 修改
            current.element = element;
        }

    }

    LinkedList.prototype.isEmpty = function () {
        return this.length == 0
    }

    LinkedList.prototype.size = function () {
        return this.length
    }

}